package com.zk.algorithm.linkedlist;

import com.zk.algorithm.Utils;
import com.zk.algorithm.bean.ListNode;
import com.zk.algorithm.factory.ListFactory;

/**
 * https://leetcode.com/problems/odd-even-linked-list/
 *
 * @author zk
 */
public class OddEventLinkedList {

    // Input: 2->1->3->5->6->4->7->NULL
    // Output: 2->3->6->7->1->5->4->NULL
    //
    // 这里奇数偶数指的是节点号
    // 2 -> 1 -> 3 -> 5 -> 6 -> 4 -> 7 -> NULL
    // 1    2    3    4    5    6    7
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // ODD -> 2 -> 1 -> 3 -> 5 -> 6 -> 4 -> 7 -> NULL
        //  ↑
        //
        // EVE -> 2 -> 1 -> 3 -> 5 -> 6 -> 4 -> 7 -> NULL
        //  ↑
        //
        ListNode oddDummy = new ListNode(-1);
        oddDummy.next = head;
        ListNode oddWalker = oddDummy;

        ListNode evenDummy = new ListNode(-1);
        ListNode evenWalker = evenDummy;

        ListNode walker = head;
        int len = 0;
        while (walker != null) {
            len++;

            if (len % 2 == 1) {
                oddWalker.next = walker;
                oddWalker = oddWalker.next;
            } else {
                evenWalker.next = walker;
                evenWalker = evenWalker.next;
            }

            walker = walker.next;
        }

        evenWalker.next = null;
        oddWalker.next = evenDummy.next;

        return oddDummy.next;
    }

    public static void main(String...args) {
        Utils.println(new OddEventLinkedList().oddEvenList(ListFactory.create(new int[]{
                2, 1, 3, 5, 6, 4, 7
        })));

        Utils.println(new OddEventLinkedList().oddEvenList(ListFactory.create(new int[]{
                2, 1, 3
        })));
    }

}
